// 版权所有2011 Go作者。版权所有。
// 此源代码的使用受BSD样式的约束
// 可以在许可证文件中找到的许可证。

package main

import (
	"fmt"
	"go/ast"
	"go/parser"
	"go/token"
	exec "internal/execabs"
	"os"
	"path/filepath"
	"reflect"
	"runtime"
	"strings"
)

// 部分类型检查器。
// None
// 它是局部的这一事实非常重要：输入是局部的
// AST和某些类型信息的描述
// 假设有一个或多个包，但不是所有的包
// 程序导入的包。检查人员正在检查
// 希望尽可能多地利用已经发生的事情
// 鉴于提供的信息不足，无法执行此操作
// 完整类型检查，但类型检查器应
// 应用可从变量派生的信息
// 声明、函数和方法返回以及类型开关
// 尽可能远，以便调用者仍能说出类型
// 指与某一特定固定点相关的表达式。
// None
// TODO（rsc、gri）：替换为go/typechecker。
// 对于go/typechecker来说，这样做可能是一个有趣的测试用例：
// 有关使用部分信息的约束将
// 可能会以有趣的方式进行锻炼。理想的界面是
// 要通过类型检查从importpath到PackageAPI文本的映射
// （Go源代码），但现在我们使用数据结构（TypeConfig，Type）。
// None
// 字符串大多使用gofmt形式。
// None
// 字段或字段列表的类型为逗号分隔的列表
// 字段的类型。例如，字段列表
// x、 y，z int
// 具有类型“int，int，int”。

// 前缀“type”是类型的类型。
// 例如，给定
// var x int
// 类型T int
// x的类型是“int”，而T的类型是“int”。
// mkType插入“type”前缀。
// getType会删除它。
// 我对它进行了类型测试。

func mkType(t string) string {
	return "type " + t
}

func getType(t string) string {
	if !isType(t) {
		return ""
	}
	return t[len("type "):]
}

func isType(t string) bool {
	return strings.HasPrefix(t, "type ")
}

// TypeConfig描述了相关类型的范围。
// 为便于创建，所有类型都由字符串引用
// 名称（例如，“reflect.Value”）。TypeByName是唯一的地方
// 解析字符串的位置。

type TypeConfig struct {
	Type map[string]*Type
	Var  map[string]string
	Func map[string]string

	// 外部从名称映射到其类型。
	// 它提供了Go源本身中不存在的其他类型。
	// 目前，唯一的附加类型是cgo生成的类型。
	External map[string]string
}

// typeof返回给定名称的类型，该名称可能为
// 表格“x”或“p.x”。
func (cfg *TypeConfig) typeof(name string) string {
	if cfg.Var != nil {
		if t := cfg.Var[name]; t != "" {
			return t
		}
	}
	if cfg.Func != nil {
		if t := cfg.Func[name]; t != "" {
			return "func()" + t
		}
	}
	return ""
}

// 类型描述类型的字段和方法。
// 如果在那里找不到字段或方法，则下一步就是它
// 在嵌入列表中查找。
type Type struct {
	Field  map[string]string // 将字段名映射到类型
	Method map[string]string // 将方法名称映射到逗号分隔的返回类型（应以“func”开头）
	Embed  []string          // 此类型嵌入的类型列表（用于其他方法）
	Def    string            // 命名类型的定义
}

// dot返回“typ.name”类型，并做出决定
// 使用cfg中的类型信息。
func (typ *Type) dot(cfg *TypeConfig, name string) string {
	if typ.Field != nil {
		if t := typ.Field[name]; t != "" {
			return t
		}
	}
	if typ.Method != nil {
		if t := typ.Method[name]; t != "" {
			return t
		}
	}

	for _, e := range typ.Embed {
		etyp := cfg.Type[e]
		if etyp != nil {
			if t := etyp.dot(cfg, name); t != "" {
				return t
			}
		}
	}

	return ""
}

// typecheck类型检查AST f，假设信息在cfg中。
// 它返回两个带有类型信息的映射：
// typeof将AST节点映射为gofmt字符串形式的类型信息。
// 将映射类型字符串指定给已指定的表达式列表
// 指定给该类型的其他类型的值。
func typecheck(cfg *TypeConfig, f *ast.File) (typeof map[interface{}]string, assign map[string][]interface{}) {
	typeof = make(map[interface{}]string)
	assign = make(map[string][]interface{})
	cfg1 := &TypeConfig{}
	*cfg1 = *cfg // 制作副本以便我们可以在本地添加
	copied := false

	// 如果我们导入“C”，则添加cgo对象的类型。
	cfg.External = map[string]string{}
	cfg1.External = cfg.External
	if imports(f, "C") {
		// 在gofmtFile（f）上运行cgo
		// 从_cgo_gotypes.go解析、提取DECL
		// 将Ctype_*类型映射到C*类型。
		err := func() error {
			txt, err := gofmtFile(f)
			if err != nil {
				return err
			}
			dir, err := os.MkdirTemp(os.TempDir(), "fix_cgo_typecheck")
			if err != nil {
				return err
			}
			defer os.RemoveAll(dir)
			err = os.WriteFile(filepath.Join(dir, "in.go"), txt, 0600)
			if err != nil {
				return err
			}
			cmd := exec.Command(filepath.Join(runtime.GOROOT(), "bin", "go"), "tool", "cgo", "-objdir", dir, "-srcdir", dir, "in.go")
			err = cmd.Run()
			if err != nil {
				return err
			}
			out, err := os.ReadFile(filepath.Join(dir, "_cgo_gotypes.go"))
			if err != nil {
				return err
			}
			cgo, err := parser.ParseFile(token.NewFileSet(), "cgo.go", out, 0)
			if err != nil {
				return err
			}
			for _, decl := range cgo.Decls {
				fn, ok := decl.(*ast.FuncDecl)
				if !ok {
					continue
				}
				if strings.HasPrefix(fn.Name.Name, "_Cfunc_") {
					var params, results []string
					for _, p := range fn.Type.Params.List {
						t := gofmt(p.Type)
						t = strings.ReplaceAll(t, "_Ctype_", "C.")
						params = append(params, t)
					}
					for _, r := range fn.Type.Results.List {
						t := gofmt(r.Type)
						t = strings.ReplaceAll(t, "_Ctype_", "C.")
						results = append(results, t)
					}
					cfg.External["C."+fn.Name.Name[7:]] = joinFunc(params, results)
				}
			}
			return nil
		}()
		if err != nil {
			fmt.Fprintf(os.Stderr, "go fix: warning: no cgo types: %s\n", err)
		}
	}

	// 收集函数声明
	for _, decl := range f.Decls {
		fn, ok := decl.(*ast.FuncDecl)
		if !ok {
			continue
		}
		typecheck1(cfg, fn.Type, typeof, assign)
		t := typeof[fn.Type]
		if fn.Recv != nil {
			// 接收器必须是一个类型。
			rcvr := typeof[fn.Recv]
			if !isType(rcvr) {
				if len(fn.Recv.List) != 1 {
					continue
				}
				rcvr = mkType(gofmt(fn.Recv.List[0].Type))
				typeof[fn.Recv.List[0].Type] = rcvr
			}
			rcvr = getType(rcvr)
			if rcvr != "" && rcvr[0] == '*' {
				rcvr = rcvr[1:]
			}
			typeof[rcvr+"."+fn.Name.Name] = t
		} else {
			if isType(t) {
				t = getType(t)
			} else {
				t = gofmt(fn.Type)
			}
			typeof[fn.Name] = t

			// 记录[fn.Name.Obj]的类型，以便将来引用fn.Name。
			typeof[fn.Name.Obj] = t
		}
	}

	// 聚集结构声明
	for _, decl := range f.Decls {
		d, ok := decl.(*ast.GenDecl)
		if ok {
			for _, s := range d.Specs {
				switch s := s.(type) {
				case *ast.TypeSpec:
					if cfg1.Type[s.Name.Name] != nil {
						break
					}
					if !copied {
						copied = true
						// 懒洋洋地复制地图：是时候了。
						cfg1.Type = make(map[string]*Type)
						for k, v := range cfg.Type {
							cfg1.Type[k] = v
						}
					}
					t := &Type{Field: map[string]string{}}
					cfg1.Type[s.Name.Name] = t
					switch st := s.Type.(type) {
					case *ast.StructType:
						for _, f := range st.Fields.List {
							for _, n := range f.Names {
								t.Field[n.Name] = gofmt(f.Type)
							}
						}
					case *ast.ArrayType, *ast.StarExpr, *ast.MapType:
						t.Def = gofmt(st)
					}
				}
			}
		}
	}

	typecheck1(cfg1, f, typeof, assign)
	return typeof, assign
}

func makeExprList(a []*ast.Ident) []ast.Expr {
	var b []ast.Expr
	for _, x := range a {
		b = append(b, x)
	}
	return b
}

// Typecheck1是typecheck的递归形式。
// 它类似于typecheck，但会在typeof中添加信息
// 而不是分配一个新的地图。
func typecheck1(cfg *TypeConfig, f interface{}, typeof map[interface{}]string, assign map[string][]interface{}) {
	// set将n的类型设置为typ。
	// 如果isDecl为true，则声明n。
	set := func(n ast.Expr, typ string, isDecl bool) {
		if typeof[n] != "" || typ == "" {
			if typeof[n] != typ {
				assign[typ] = append(assign[typ], n)
			}
			return
		}
		typeof[n] = typ

		// 如果我们从x的声明中获得了typ
		// 将类型传播到所有用途。
		// 这个isDecl案件在这里是个骗局，但它使
		// 在某些情况下，因为没有注意到
		// 结构字段。真正的类型检查器将是
		// 更准确，所以我们不需要作弊。
		if id, ok := n.(*ast.Ident); ok && id.Obj != nil && (isDecl || typeof[id.Obj] == "") {
			typeof[id.Obj] = typ
		}
	}

	// 类型检查分配lhs=rhs。
	// 如果isDecl为true，则为：=以便我们可以更新
	// lhs所指对象的类型。
	typecheckAssign := func(lhs, rhs []ast.Expr, isDecl bool) {
		if len(lhs) > 1 && len(rhs) == 1 {
			if _, ok := rhs[0].(*ast.CallExpr); ok {
				t := split(typeof[rhs[0]])
				// 列表长度应相同，但不能相同；配对可以配对的东西。
				for i := 0; i < len(lhs) && i < len(t); i++ {
					set(lhs[i], t[i], isDecl)
				}
				return
			}
		}
		if len(lhs) == 1 && len(rhs) == 2 {
			// x=y，好的
			rhs = rhs[:1]
		} else if len(lhs) == 2 && len(rhs) == 1 {
			// x、 ok=y
			lhs = lhs[:1]
		}

		// 尽可能地匹配。
		for i := 0; i < len(lhs) && i < len(rhs); i++ {
			x, y := lhs[i], rhs[i]
			if typeof[y] != "" {
				set(x, typeof[y], isDecl)
			} else {
				set(y, typeof[x], false)
			}
		}
	}

	expand := func(s string) string {
		typ := cfg.Type[s]
		if typ != nil && typ.Def != "" {
			return typ.Def
		}
		return s
	}

	// 主类型检查是实现的递归算法
	// 通过walkbeforefeater（n，before，after）。
	// 大部分是自下而上的，但在一些我们需要的地方
	// 了解我们正在检查的函数的类型。
	// before函数将该信息记录在
	// curfn堆栈。
	var curfn []*ast.FuncType

	before := func(n interface{}) {
		// 堆栈上的push函数类型
		switch n := n.(type) {
		case *ast.FuncDecl:
			curfn = append(curfn, n.Type)
		case *ast.FuncLit:
			curfn = append(curfn, n.Type)
		}
	}

	// 之后是真正的类型检查器。
	after := func(n interface{}) {
		if n == nil {
			return
		}
		if false && reflect.TypeOf(n).Kind() == reflect.Ptr { // 调试跟踪
			defer func() {
				if t := typeof[n]; t != "" {
					pos := fset.Position(n.(ast.Node).Pos())
					fmt.Fprintf(os.Stderr, "%s: typeof[%s] = %s\n", pos, gofmt(n), t)
				}
			}()
		}

		switch n := n.(type) {
		case *ast.FuncDecl, *ast.FuncLit:
			// pop函数类型离开堆栈
			curfn = curfn[:len(curfn)-1]

		case *ast.FuncType:
			typeof[n] = mkType(joinFunc(split(typeof[n.Params]), split(typeof[n.Results])))

		case *ast.FieldList:
			// 字段列表是子列表的串联。
			t := ""
			for _, field := range n.List {
				if t != "" {
					t += ", "
				}
				t += typeof[field]
			}
			typeof[n] = t

		case *ast.Field:
			// 字段是每个名称的类型的一个实例。
			all := ""
			t := typeof[n.Type]
			if !isType(t) {
				// 创建一个类型，因为它通常是*T或*p.T
				// 我们可能会关心这种类型。
				t = mkType(gofmt(n.Type))
				typeof[n.Type] = t
			}
			t = getType(t)
			if len(n.Names) == 0 {
				all = t
			} else {
				for _, id := range n.Names {
					if all != "" {
						all += ", "
					}
					all += t
					typeof[id.Obj] = t
					typeof[id] = t
				}
			}
			typeof[n] = all

		case *ast.ValueSpec:
			// var声明。使用类型（如果存在）。
			if n.Type != nil {
				t := typeof[n.Type]
				if !isType(t) {
					t = mkType(gofmt(n.Type))
					typeof[n.Type] = t
				}
				t = getType(t)
				for _, id := range n.Names {
					set(id, t, true)
				}
			}
			// 现在将其视为作业。
			typecheckAssign(makeExprList(n.Names), n.Values, true)

		case *ast.AssignStmt:
			typecheckAssign(n.Lhs, n.Rhs, n.Tok == token.DEFINE)

		case *ast.Ident:
			// 标识符可以从基础对象获取其类型。
			if t := typeof[n.Obj]; t != "" {
				typeof[n] = t
			}

		case *ast.SelectorExpr:
			// 字段或方法。
			name := n.Sel.Name
			if t := typeof[n.X]; t != "" {
				t = strings.TrimPrefix(t, "*") // 含蓄的*
				if typ := cfg.Type[t]; typ != nil {
					if t := typ.dot(cfg, name); t != "" {
						typeof[n] = t
						return
					}
				}
				tt := typeof[t+"."+name]
				if isType(tt) {
					typeof[n] = getType(tt)
					return
				}
			}
			// 包选择器。
			if x, ok := n.X.(*ast.Ident); ok && x.Obj == nil {
				str := x.Name + "." + name
				if cfg.Type[str] != nil {
					typeof[n] = mkType(str)
					return
				}
				if t := cfg.typeof(x.Name + "." + name); t != "" {
					typeof[n] = t
					return
				}
			}

		case *ast.CallExpr:
			// make（T）具有T型。
			if isTopName(n.Fun, "make") && len(n.Args) >= 1 {
				typeof[n] = gofmt(n.Args[0])
				return
			}
			// 新（T）具有*T类型
			if isTopName(n.Fun, "new") && len(n.Args) == 1 {
				typeof[n] = "*" + gofmt(n.Args[0])
				return
			}
			// 否则，请使用函数类型来确定参数。
			t := typeof[n.Fun]
			if t == "" {
				t = cfg.External[gofmt(n.Fun)]
			}
			in, out := splitFunc(t)
			if in == nil && out == nil {
				return
			}
			typeof[n] = join(out)
			for i, arg := range n.Args {
				if i >= len(in) {
					break
				}
				if typeof[arg] == "" {
					typeof[arg] = in[i]
				}
			}

		case *ast.TypeAssertExpr:
			// x、 （类型）的类型为x。
			if n.Type == nil {
				typeof[n] = typeof[n.X]
				return
			}
			// x、 （T）具有T型。
			if t := typeof[n.Type]; isType(t) {
				typeof[n] = getType(t)
			} else {
				typeof[n] = gofmt(n.Type)
			}

		case *ast.SliceExpr:
			// x[i:j]具有x的类型。
			typeof[n] = typeof[n.X]

		case *ast.IndexExpr:
			// x[i]的键类型为x的类型。
			t := expand(typeof[n.X])
			if strings.HasPrefix(t, "[") || strings.HasPrefix(t, "map[") {
				// 惰性：假设数组中没有嵌套[]
				// 长度或映射键类型。
				if i := strings.Index(t, "]"); i >= 0 {
					typeof[n] = t[i+1:]
				}
			}

		case *ast.StarExpr:
			// *当x是表达式时，类型为*T的x的x具有类型T。
			// 当*x是一个类型时，我们不使用结果，但是
			// 还是算算吧。
			t := expand(typeof[n.X])
			if isType(t) {
				typeof[n] = "type *" + getType(t)
			} else if strings.HasPrefix(t, "*") {
				typeof[n] = t[len("*"):]
			}

		case *ast.UnaryExpr:
			// &类型为T的x的x具有类型*T。
			t := typeof[n.X]
			if t != "" && n.Op == token.AND {
				typeof[n] = "*" + t
			}

		case *ast.CompositeLit:
			// T{…}具有类型T。
			typeof[n] = gofmt(n.Type)

			// 将类型向下传播到复合文字中使用的值。
			t := expand(typeof[n])
			if strings.HasPrefix(t, "[") { // 数组或切片
				// 惰性：假设数组长度中没有嵌套[]。
				if i := strings.Index(t, "]"); i >= 0 {
					et := t[i+1:]
					for _, e := range n.Elts {
						if kv, ok := e.(*ast.KeyValueExpr); ok {
							e = kv.Value
						}
						if typeof[e] == "" {
							typeof[e] = et
						}
					}
				}
			}
			if strings.HasPrefix(t, "map[") { // 地图
				// 惰性：假设映射键类型中没有嵌套[]。
				if i := strings.Index(t, "]"); i >= 0 {
					kt, vt := t[4:i], t[i+1:]
					for _, e := range n.Elts {
						if kv, ok := e.(*ast.KeyValueExpr); ok {
							if typeof[kv.Key] == "" {
								typeof[kv.Key] = kt
							}
							if typeof[kv.Value] == "" {
								typeof[kv.Value] = vt
							}
						}
					}
				}
			}
			if typ := cfg.Type[t]; typ != nil && len(typ.Field) > 0 { // 结构
				for _, e := range n.Elts {
					if kv, ok := e.(*ast.KeyValueExpr); ok {
						if ft := typ.Field[fmt.Sprintf("%s", kv.Key)]; ft != "" {
							if typeof[kv.Value] == "" {
								typeof[kv.Value] = ft
							}
						}
					}
				}
			}

		case *ast.ParenExpr:
			// （x） 有x型。
			typeof[n] = typeof[n.X]

		case *ast.RangeStmt:
			t := expand(typeof[n.X])
			if t == "" {
				return
			}
			var key, value string
			if t == "string" {
				key, value = "int", "rune"
			} else if strings.HasPrefix(t, "[") {
				key = "int"
				if i := strings.Index(t, "]"); i >= 0 {
					value = t[i+1:]
				}
			} else if strings.HasPrefix(t, "map[") {
				if i := strings.Index(t, "]"); i >= 0 {
					key, value = t[4:i], t[i+1:]
				}
			}
			changed := false
			if n.Key != nil && key != "" {
				changed = true
				set(n.Key, key, n.Tok == token.DEFINE)
			}
			if n.Value != nil && value != "" {
				changed = true
				set(n.Value, value, n.Tok == token.DEFINE)
			}
			// 丑陋的视力障碍：已经检查过身体类型。
			// 现在我们有了类型信息，再做一次。
			if changed {
				typecheck1(cfg, n.Body, typeof, assign)
			}

		case *ast.TypeSwitchStmt:
			// 类型开关中每种情况下的变量变化类型，
			// 但是go/parser只生成一个变量。
			// 对每种情况重复进行类型检查，以获得更精确的结果
			// 类型信息。
			as, ok := n.Assign.(*ast.AssignStmt)
			if !ok {
				return
			}
			varx, ok := as.Lhs[0].(*ast.Ident)
			if !ok {
				return
			}
			t := typeof[varx]
			for _, cas := range n.Body.List {
				cas := cas.(*ast.CaseClause)
				if len(cas.List) == 1 {
					// 变量只有在存在时才具有特定类型
					// 案例列表中只有一种类型。
					if tt := typeof[cas.List[0]]; isType(tt) {
						tt = getType(tt)
						typeof[varx] = tt
						typeof[varx.Obj] = tt
						typecheck1(cfg, cas.Body, typeof, assign)
					}
				}
			}
			// 恢复t。
			typeof[varx] = t
			typeof[varx.Obj] = t

		case *ast.ReturnStmt:
			if len(curfn) == 0 {
				// 可能不会发生。
				return
			}
			f := curfn[len(curfn)-1]
			res := n.Results
			if f.Results != nil {
				t := split(typeof[f.Results])
				for i := 0; i < len(res) && i < len(t); i++ {
					set(res[i], t[i], false)
				}
			}

		case *ast.BinaryExpr:
			// 跨需要两个相同类型的参数的二进制操作传播类型。
			switch n.Op {
			case token.EQL, token.NEQ: // TODO:更多案例。这对于cftype修复就足够了。
				if typeof[n.X] != "" && typeof[n.Y] == "" {
					typeof[n.Y] = typeof[n.X]
				}
				if typeof[n.X] == "" && typeof[n.Y] != "" {
					typeof[n.X] = typeof[n.Y]
				}
			}
		}
	}
	walkBeforeAfter(f, before, after)
}

// 在函数类型字符串和类型列表之间转换。
// 使用字符串会使这变得有点困难，但是
// 代码的其余部分很简单。这一切都会过去的
// 当我们可以直接使用go/typechecker时。

// splitFunc将“func（x，y，z）（a，b，c）”拆分为[“x”，“y”，“z”]和[“a”，“b”，“c”]。
func splitFunc(s string) (in, out []string) {
	if !strings.HasPrefix(s, "func(") {
		return nil, nil
	}

	i := len("func(") // “in”参数开头的索引
	nparen := 0
	for j := i; j < len(s); j++ {
		switch s[j] {
		case '(':
			nparen++
		case ')':
			nparen--
			if nparen < 0 {
				// 找到参数列表的结尾
				out := strings.TrimSpace(s[j+1:])
				if len(out) >= 2 && out[0] == '(' && out[len(out)-1] == ')' {
					out = out[1 : len(out)-1]
				}
				return split(s[i:j]), split(out)
			}
		}
	}
	return nil, nil
}

// joinFunc是splitFunc的逆函数。
func joinFunc(in, out []string) string {
	outs := ""
	if len(out) == 1 {
		outs = " " + out[0]
	} else if len(out) > 1 {
		outs = " (" + join(out) + ")"
	}
	return "func(" + join(in) + ")" + outs
}

// 拆分将“int，float”拆分为[“int”，“float”]并将“”拆分为[]。
func split(s string) []string {
	out := []string{}
	i := 0 // 正在扫描的当前类型是s[i:j]。
	nparen := 0
	for j := 0; j < len(s); j++ {
		switch s[j] {
		case ' ':
			if i == j {
				i++
			}
		case '(':
			nparen++
		case ')':
			nparen--
			if nparen < 0 {
				// 可能不会发生
				return nil
			}
		case ',':
			if nparen == 0 {
				if i < j {
					out = append(out, s[i:j])
				}
				i = j + 1
			}
		}
	}
	if nparen != 0 {
		// 可能不会发生
		return nil
	}
	if i < len(s) {
		out = append(out, s[i:])
	}
	return out
}

// join是split的反义词。
func join(x []string) string {
	return strings.Join(x, ", ")
}
